package com.sheng.leetcode.year2023.month05.day31;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/05/31
 * <p>
 * 1130. 叶值的最小代价生成树<p>
 * <p>
 * 给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：<p>
 * 每个节点都有 0 个或是 2 个子节点。<p>
 * 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。<p>
 * 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。<p>
 * 在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。<p>
 * 如果一个节点有 0 个子节点，那么该节点为叶节点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：arr = [6,2,4]<p>
 * 输出：32<p>
 * 解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：arr = [4,11]<p>
 * 输出：44<p>
 * <p>
 * 提示：<p>
 * 2 <= arr.length <= 40<p>
 * 1 <= arr[i] <= 15<p>
 * 答案保证是一个 32 位带符号整数，即小于 2^31 。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values">1130. 叶值的最小代价生成树</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1130 {

    @Test
    public void test01() {
        // 2 * 6 + 6 * 4  或  2 * 4 + 4 * 6
//        int[] arr = {6, 2, 4};
        int[] arr = {4, 11};
        // 1 * 2 + 2 * 3 + 4 * 5 + 3 * 5
        System.out.println(new Solution().mctFromLeafValues(arr));
    }
}

class Solution {
    public int mctFromLeafValues(int[] arr) {
        // 解读：数组 arr 中的元素为从左到右的叶结点的顺序，其父节点为左右叶结点中最大值的乘积
        // 现要求获取非叶结点的最小可能总和
        int n = arr.length;
        // f[i][j] 表示数组 arr 中下标范围 [i, j] 内的所有非叶结点的值的最小可能总和
        int[][] f = new int[n][n];
        // g[i][j] 表示数组 arr 中下标范围 [i, j] 内的所有叶结点的最大值
        int[][] g = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            g[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                g[i][j] = Math.max(g[i][j - 1], arr[j]);
                f[i][j] = 1 << 30;
                for (int k = i; k < j; k++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j]);
                }
            }
        }
        return f[0][n - 1];
    }
}
